%% header
%% \rightheader{\emph{Transform and Conquer} - \thepage\}

\chapter{Transform and Conquer}

\section{Pendahuluan}

Kadang kita menghadapi sebuah masalah yang dapat diselesaikan dengan lebih mudah jika masalah tersebut diubah menjadi bentuk masalah yang lain. Dalam bab ini, dibahas kelompok masalah yang dapat dipecahkan dengan menggunakan teknik \emph{Transform and Conquer}. Beberapa contoh masalah yang tergolong dalam kelompok ini antara lain mencari solusi sistem persamaan linier dengan eliminasi Gauss (Subbab~\ref{sect:eliminiasi-gauss}).

Secara konseptual, teknik \emph{transform and conquer} mengubah masalah awal menjadi masalah lain, dalam kebanyakan hal, merupakan masalah yang lebih sederhana untuk dipecahkan. Satu hal yang perlu diperhatikan di sini adalah masalah baru yang didapatkan dari hasil transformasi ini tidak menghilangkan inti masalah awal.

Masalah hasil transformasi yang lebih sederhana dari hasil transformasi ini dapat dicari solusinya dengan cara yang mudah. Solusi yang didapatkan nantinya akan ditransformasikan kembali menjadi solusi dari masalah awal yang diberikan. Hal ini dapat dirangkum seperti dalam Gambar~\ref{fig:transform-and-conquer}.

\begin{figure}
\label{fig:transform-and-conquer} \caption{Kerangka kerja teknik Transform and Conquer.}
\end{figure}


\section{Eliminasi Gauss} \label{sect:eliminasi-gauss}

Salah satu masalah yang bisa dipecahkan dalam kerangka kerja \emph{Transform and Conquer} adalah Eliminasi Gauss. Dari mata kuliah Aljabar Linier, kita ketahui bersama, Eliminasi Gauss adalah sebuah cara untuk mencari solusi dari sebuah sistem persamaan linier.

Sebuah sistem persamaan linier adalah 2 atau lebih persamaan yang memiliki nilai pemecahan yang sama. Dari pelajaran di SMU, sistem persamaan linier semacam ini dikenal dengan teknik substitusi. Sebagai contoh perhatikan sistem persamaan berikut ini:

\begin{eqnarray}
  2 x_1 & + x_2 & = 2 \\
  -2 x_1 & + 4 x_2 = 4 \\
\end{eqnarray}

Di SMU, sistem persamaan tersebut dapat diselesaikan dengan menggunakan teknik substitusi, yaitu mengubah bentuk persamaan pertama menjadi

\[ x_2 = 2 - 2 x_1 \]

yang kemudian kita gunakan untuk mensubstitusi nilai $x_2$ di persamaan kedua:

\[ -2 x_1 + 4 (2 - 2 x_1) = 4 \]

Dari sini kita dapat menemukan nilai $x_1$, yang kemudian dapat kita gunakan untuk mencari nilai $x_2$.

Jika sistem persamaan yang ingin dicari solusinya hanya terdiri atas 2 persamaan dengan 2 variabel ($x_1$ dan $x_2$), teknik substitusi dapat digunakan. Namun untuk sistem persamaan linier yang lebih kompleks, terdiri atas $n$ persamaan dengan $n$ variabel ($x_1, x_2, \ldots x_n$), maka teknik substitusi tidak cocok untuk digunakan mencari solusinya.

Untuk mencari solusi sebuah sistem persamaan linier yang terdiri atas $n$ persamaan dengan $n$ variabel, salah satu cara yang dapat digunakan adalah metode \textbf{Eliminasi Gauss} (\emph{Gauss Elimination}). Untuk membahas metode ini, kita ambil sebuah contoh sistem persamaan linier yang terdiri atas $3$ variabel:

% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabeqaduaaaaqaaiaaikdacaWG4bWaaS
% baaSqaaiaaigdaaeqaaaGcbaGaeyOeI0IaamiEamaaBaaaleaacaaI
% YaaabeaaaOqaaiabgUcaRiaadIhadaWgaaWcbaGaaG4maaqabaaake
% aacqGH9aqpaeaacaaIXaaabaGaaGinaiaadIhadaWgaaWcbaGaaGym
% aaqabaaakeaacqGHRaWkcaWG4bWaaSbaaSqaaiaaikdaaeqaaaGcba
% GaeyOeI0IaamiEamaaBaaaleaacaaIZaaabeaaaOqaaiabg2da9aqa
% aiaaiwdaaeaacaaIXaGaamiEamaaBaaaleaacaaIXaaabeaaaOqaai
% abgUcaRiaadIhadaWgaaWcbaGaaGOmaaqabaaakeaacqGHRaWkcaWG
% 4bWaaSbaaSqaaiaaiodaaeqaaaGcbaGaeyypa0dabaGaaGimaaaaaa
% a!5007!
\[
\begin{array}{*{20}c}
   {2x_1 } & { - x_2 } & { + x_3 } &  =  & 1  \\
   {4x_1 } & { + x_2 } & { - x_3 } &  =  & 5  \\
   {1x_1 } & { + x_2 } & { + x_3 } &  =  & 0  \\
\end{array}
\]

Untuk mencari nilai-nilai $x_1$, $x_2$, dan $x_3$ yang tepat, kita gunakan metode Eliminasi Gauss terhadap sistem persamaan tersebut di atas. Sebelum kita bahas bagaimana menggunakan teknik eliminasi ini, kita perhatikan dulu bahwa sistem persamaan tersebut sebenarnya bisa dilihat sebagai perkalian dari sebuah matriks koefisien dengan sebuah matriks variabel.

Jika kita misalkan matriks $A$ adalah matriks koefisien yang elemen-elemennya sebagai berikut
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaamaabmaabaqbaeqabmWaaaqaaiaaikdaae
% aacqGHsislcaaIXaaabaGaaGymaaqaaiaaisdaaeaacaaIXaaabaGa
% eyOeI0IaaGymaaqaaiaaigdaaeaacaaIXaaabaGaaGymaaaaaiaawI
% cacaGLPaaaaaa!3BB5!
\[
\left[ {\begin{array}{*{20}c}
   2 & { - 1} & 1  \\
   4 & 1 & { - 1}  \\
   1 & 1 & 1  \\
\end{array}} \right]
\]
lalu matriks $x$ adalah matriks kolom yang berisi variabel-variabel di dalam sistem persamaan
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaamaadmaabaqbaeqabmqaaaqaaiaadIhada
% WgaaWcbaGaaGymaaqabaaakeaacaWG4bWaaSbaaSqaaiaaikdaaeqa
% aaGcbaGaamiEamaaBaaaleaacaaIZaaabeaaaaaakiaawUfacaGLDb
% aaaaa!3972!
\[
\left[ {\begin{array}{*{20}c}
   {x_1 }  \\
   {x_2 }  \\
   {x_3 }  \\
\end{array}} \right]
\]
dan matriks $b$ adalah
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaamaadmaabaqbaeqabmqaaaqaaiaaigdaae
% aacaaI1aaabaGaaGimaaaaaiaawUfacaGLDbaaaaa!35D9!
\[
\left[ {\begin{array}{*{20}c}
   1  \\
   5  \\
   0  \\
\end{array}} \right]
\]
maka sistem persamaan tersebut di atas dapat kita tuliskan sebagai sebuah operasi perkalian matriks
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadgeacqGHflY1caWG4bGaeyypa0Jaam
% Oyaaaa!379E!
\[
A \cdot x = b
\]

Teknik eliminasi Gauss mengambil matriks koefisien $A$ yang diperluas dengan menambahkan matriks kolom $b$ sehingga menjadi sebuah matriks berukuran $4 \times 3$ seperti berikut
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaamaadmaabaWaaqGaaeaafaqabeWadaaaba
% GaaGOmaaqaaiabgkHiTiaaigdaaeaacaaIXaaabaGaaGinaaqaaiaa
% igdaaeaacqGHsislcaaIXaaabaGaaGymaaqaaiaaigdaaeaacaaIXa
% aaaaGaayjcSdqbaeqabmqaaaqaaiaaigdaaeaacaaI1aaabaGaaGim
% aaaaaiaawUfacaGLDbaaaaa!3FF7!
\[
\left[ {\left. {\begin{array}{*{20}c}
   2 & { - 1} & 1  \\
   4 & 1 & { - 1}  \\
   1 & 1 & 1  \\
\end{array}} \right|\begin{array}{*{20}c}
   1  \\
   5  \\
   0  \\
\end{array}} \right]
\]



\section{Latihan} \label{sect:exercise-gaussian-elimination}

% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabeqaduaaaaqaaiaadIhadaWgaaWcba
% GaaGymaaqabaaakeaacqGHRaWkcaWG4bWaaSbaaSqaaiaaikdaaeqa
% aaGcbaGaey4kaSIaamiEamaaBaaaleaacaaIZaaabeaaaOqaaiabg2
% da9aqaaiaaikdaaeaacaaIYaGaamiEamaaBaaaleaacaaIXaaabeaa
% aOqaaiabgUcaRiaadIhadaWgaaWcbaGaaGOmaaqabaaakeaacqGHRa
% WkcaWG4bWaaSbaaSqaaiaaiodaaeqaaaGcbaGaeyypa0dabaGaaG4m
% aaqaaiaadIhadaWgaaWcbaGaaGymaaqabaaakeaacqGHsislcaWG4b
% WaaSbaaSqaaiaaikdaaeqaaaGcbaGaey4kaSIaaG4maiaadIhadaWg
% aaWcbaGaaG4maaqabaaakeaacqGH9aqpaeaacaaI4aaaaaaa!4F47!
\[
\begin{array}{*{20}c}
   {x_1 } & { + x_2 } & { + x_3 } &  =  & 2  \\
   {2x_1 } & { + x_2 } & { + x_3 } &  =  & 3  \\
   {x_1 } & { - x_2 } & { + 3x_3 } &  =  & 8  \\
\end{array}
\]
